The present invention relates to the management of computer databases, and more particularly to a method for avoiding deadlock situations during index updates in a database application which uses a unique key index and the pseudo-deletion of index entries.
Database applications are an important use of modem computer systems, and especially modem networked computer systems. Among other uses, computer databases store business data such as inventories, sales information, personnel information, and the like. One advantage of implementing a database on a networked computer system is to provide the ability for multiple users, often at multiple locations or access points, to work essentially simultaneously with a single shared database. For example, a retail store chain may use a single shared database which is accessed by the various individual store outlets. A first store may add newly acquired merchandise to the inventory table of a shared database. The inventory table is accessible to all the stores in the chain, and a second store in the chain may advantageously search the inventory table, locate the merchandise being held at the first store, and request a reallocation of some portion of this merchandise to the second store if sales information, perhaps recorded in a sales table of the same shared database, indicates that the merchandise may be more effectively retailed at the second store. Thus, the shared and networked database permits more efficient allocation and use of the shared resources of the retail store chain. Of course, similar benefits arise from the use of networked databases in conjunction with other types of distributed businesses, as well as in conjunction with geographically distributed organizations such as religious and political organizations.
With reference to FIG. 1, an exemplary database application 10 for management of a sporting goods retail organization is schematically shown in simplified form. A database 12 includes a plurality of table objects, namely an inventory table 14, a sales table 16, and a human resources table 18. Each table contains a specific number of columns and some unordered rows, as shown for example in a more detailed schematic of the inventory table 14′. The detailed schematic of the inventory table 14′ shows that it includes four data columns, namely a store (“Store”) column 22, an item (“Item”) column 24, a model (“Model”) column 26, and a quantity (“Qty”) column 28. Of course, other columns may be included such as a product manufacturer column, and the number and type of columns is typically different for each table object. The number and identity of columns in a table defines the structure of that table, and is not generally modifiable by ordinary database users, although a database administrator or other individual with high-level access privileges may be able to modify the table structure. Similarly, the number and identity of the tables are normally fixed for ordinary users, and are modifiable only by users with special access privileges.
The data in each table typically consists of unordered rows formed according to the table column structure. Each row is indexed by a record index (RID) 30 as illustrated in the detailed schematic of the inventory table 14′. The rows are not typically arranged in any particular order. For example, in the exemplary inventory table 14′ a blank row 40 with RID=0014 is interspersed among the rows containing data. Blank row 40 may have resulted from a deleted record at the record index RID=0014. Users with ordinary access privileges typically have the ability to add, delete, or change rows of a table, typically within suitable predefined bounds.
To provide organization of the database, a unique key index 42 is maintained, with separate indexes for each table. Thus, the unique key index 42 includes an inventory table index 44, a sales table index 46, and a human resources table index 48. Each table index contains a specific number of columns and some rows, as shown for example in a more detailed schematic of the inventory table index 44′. The detailed schematic of the inventory table index 44′ shows that it includes three columns, namely a store (“Store”) column 52, a model (“Model”) column 54, and a record index (“RID”) column 56. In the example, each row of the inventory table index 44′ corresponds to a row of the inventory table 14′ but contains only the store and model information of that row, as well as the table row RID. Thus, the inventory table index 44 indexes the inventory table 14 using the store 22 and the model 26 columns of the inventory table 14, and the table row RID serves as the pointer to the table row.
The ordered column combination: (store 22, model 26) is often called the index key. To be considered a unique index key, the number and type of table columns defining the key must guarantee that each index row identifies a unique table row. Thus, inventory table index 44 could not use as an index key the ordered column combination: (store 22, item 24), as this is not a unique key (e.g., RID=0012 and RID=0015 both include store=East and item=skis). Of course, an index key is not limited to two columns, but may include as few or as many columns as is necessary to define a unique key.
An important component of a database application, and particularly of a networked database application, is the database management system (DBMS) 60. The DBMS controls the storage, retrieval, and modification of data in the database, ensures that retrieved data is current, and that data modifications do not compromise the integrity of the database. For example, the DBMS ensures that the unique key rule described above is obeyed whenever a table index is modified. For instance, the DBMS prevents entry of a new record in inventory table 14 at RID=0014 with a store value of “West” and a model value of “XS500”, as this entry would conflict with the record at RID=0010 which already has this key value.
In the exemplary schematic of FIG. 1, the DBMS 60 includes four components: a transaction manager 62, a data manager 64, an index manager 66, and a lock manager 68. It is to be appreciated that the illustrated DBMS 60 is exemplary and highly simplified in contrast to an actual DBMS used with a commercial database. Commercial database DBMS may include additional components, such as components to store and manage the database history, to produce printed reports, and the like.
In operation, the transaction manager 62 receives transaction requests. The transaction manager 62 assigns an identifier to the transaction, monitors the progress of each transaction, and is responsible for transaction completion, or for transaction failure recovery in the event that the transaction cannot be completed successfully. Typical transactions of particular interest herein include delete transactions and insert transactions, whereby records are deleted or inserted into a table object. However, it is to be appreciated that transactions may be more complex and may include composite transactions with multiple delete and/or insert elements, as well as record modification operations and the like. Single transactions can also interact with multiple table objects. For example, a transaction which records a sale by the South store of one model MD100 ski would typically include updating of at least the sales table 16, wherein the sale is recorded, and the inventory table 14. The inventory table 14′ update reduces the quantity column 28 value of row RID=0013 from “40” to “39” to reflect the inventory reduction at the South store resulting from the sale of one model MD100 ski. The transaction manager 62 communicates with both the data manager 64 and the index manager 66, which control modification of the database 12 and the unique key index 42, respectively.
The simplified DBMS 60 also includes a lock manager 68. The lock manager 68 limits access to the database 12 by requiring that DBMS components obtain a lock on the target row or rows prior to accessing said rows. Lock types which are available include at least exclusive locks—“X-locks” and shared locks—“S-locks”. These locks may be placed on rows, tables, or other database elements depending upon the DBMS configuration. Typically, X-locks are granted to transactions which modify a row or rows (including insert and delete operations), gain access to the target tables through the lock manager 68 using an exclusive lock (“X-lock”) request. Transactions which only read the contents of a row or rows without modifying the contents gain access to the data using shared lock (“S-lock”) requests.
The lock manager 68 ensures the integrity of the database 12 by issuing locks based upon lock compatibility to prevent multiple transactions from accessing the data simultaneously. For example, the lock manager will not grant more than one X-lock request for a single table row because concurrent X-locks on the same row could result in data inconsistencies as different data is written by the different transactions holding the X-locks. Thus, relative to table rows an X-lock is incompatible with another X-lock, so that after a first X-lock is placed on a first row, the lock manager denies requests for subsequent X-locks to that first row until the first X-lock is removed. However, two or more transaction requesting S-locks are typically compatible, as no inconsistency will result from two different processes that merely read a single record essentially simultaneously without modifying the record. The lock manager therefore typically grants a second S-lock to a row which already has one S-lock applied.
The prior art teaches the use of lock managers to ensure the integrity of the database data. Concurrent transactions are prevented from corrupting the data through the issuance of locks based upon lock compatibility. However, prior art methods fail to prevent certain “deadlock” situations which may arise when essentially simultaneous transactions compete for lock request control over the same rows. In these cases, two different transactions may attempt to place locks on the same table rows, and the resulting interference results in both transactions competing for the data being suspended indefinitely causing a system deadlock.
There is a need, therefore, to provide an improved database management system and method which overcomes these deadlock limitations.